#define _CRT_SECURE_NO_WARNINGS 2
#include<iostream>
#include<ctime>
#include<algorithm>

using namespace std;

void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}

//void QuickSort(int arr[], int l,int r)
//{
//	if (l >= r)	return;
//	int rand_index = l + rand() % (r - l+1);
//	int mid = arr[rand_index];
//	int left = l, cur = l, right = r;
//	while (cur <= right)
//	{
//		if (arr[cur] > mid)	swap(arr[cur], arr[right--]);
//		else if (arr[cur] < mid)	swap(arr[left++], arr[cur++]);
//		else	cur++;
//	}
//
//	QuickSort(arr, l, left - 1);
//	QuickSort(arr, right + 1, r);
//}

void QuickSort(int arr[], int  l, int r)
{
	if (l >= r)	return;
	int index = l + rand() % (r - l + 1);
	int key = arr[index];
	int left = l - 1, cur = l, right = r + 1;
	while (cur < right)
	{
		if (arr[cur] > key)	swap(arr[--right], arr[cur]);
		else if (arr[cur] < key)	swap(arr[++left], arr[cur++]);
		else cur++;
	}
	//[l,left],[left+1,right-1],[right,r];
	QuickSort(arr, l, left);
	QuickSort(arr, right, r);
}

int main()
{
	srand(time(nullptr));
	int arr[] = { 4,5,9,-1,9,0 };
	QuickSort(arr,0,5);
	Print(arr, 6);
	return 0;
}